

			APARATI CETATEA - SOLUTIE
		       ---------------------------

	Numarul minim de osteni care trebuie plasati este egal cu valoarea fluxului maxim in multi-
graful orientat dat de problema (in care sursa este orasul Brasov), iar destinatia este orasul Me-
dias). Demonstratia acestui fapt este foarte usor de intuit daca se cunoaste algoritmul Ford-Ful-
kerson de aflare a fluxului maxim intr-un graf.

	Demonstratia se face in 2 etape:

ETAPA 1
	Vom arata ca sunt suficienti FM (FM reprezinta valoarea fluxului maxim) osteni pentru a
bloca accesul de la sursa la destinatie.

ETAPA 2
	Vom arata ca nu putem bloca accesul de la sursa la destinatie cu mai putin de FM osteni.

	Etapa 2 este foarte simplu de aratat. Sa presupunem prin reducere la absurd ca putem bloca
accesul de la sursa la destinatie cu un numar de doar S osteni (S<FM). Vom elimina arcele selectate
(cele pe care vom amplasa osteni) din graful initial. Cu toate acestea, datorita modului de opera-
re a algoritmului Ford-Fulkerson, vom reusi sa mai gasim drumuri de la sursa la destinatie, cu o
valoare totala de cel putin FM-S. Astfel am gasit o contradictie cu ipoteza ca cei S osteni pot
bloca accesul de la sursa la destinatie.

	Etapa 1 o vom demonstra prin selectarea efectiva a unui numar de arce avand suma costurilor
FM si care blocheaza accesul de la sursa la destinatie. Pentru aceasta vom considera multimea A a
nodurilor la care s-a ajuns la ultima iteratie a algoritmului Ford-Fulkerson. Fie X multimea var-
furilor grafului initial si V multimea arcelor grafului initial. Atunci multimea arcelor (i,j) cu
proprietatea ca (i,j) apartine lui V, i apartine lui S si j apartine lui X\S este o multime de
arce cu proprietatile cerute.
	In afara celor spuse mai sus, mai existau probleme referitoare la memorarea grafului, in
asa fel incat algoritmul Ford Fulkerson sa fie cat mai rapid. Clasica matrice de adiacenta devenea,
in cazul dimensiunii mari a datelor de intrare, imposibil de utilizat. O posibila solutie era im-
plementarea folosind listele de vecini (una pentru muchiile reale si una pentru muchiile inverse)
cu legaturi intre ele, pentru a putea actualiza rapid drumurile gasite la fiecare iteratie a al-
goritmului Ford-Fulkerson.